// 交换变量
function swap(arr, i, j) {
  // 利用中间变量交互
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
  // 利用es6解构语法交换
  // [arr[i], arr[j]] = [arr[j], arr[i]]
}

{
  // 冒泡排序
  // 思路：第一次循环，开始比较当前元素和下一个元素的大小，如果比下一个小或者相等，则不交换两个元素的位置；
  // 若比下一个元素大的话，则交换两个元素。遍历整个数组，重复以上操作
  const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

  function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
      for (let j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
        }
      }
    }
    return arr;
  }
  // 时间复杂度是O(n^2)
  // 空间复扎渡O(1) 辅助空间为常数

  // 改进
  // 对冒泡排序进行优化改进，使得时间复杂度在大多数顺序的情况下，减小到O(n)
  // 加一个标志位，，如果没有进行交换，将标志位置为false，标识排序完成
  function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
      let flag = false;
      for (let j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
          flag = true;
        }
      }

      if (!flag) {
        break;
      }
    }
    return arr;
  }
  console.log(bubbleSort(arr));
}

{
  // 选择排序
  // 思路，第一遍选择最小的元素，与第一个元素交换，第二遍选择，从第二个元素开始找最小的，与第二个元素进行交换；依次循环，完成排序

  function selectionSort(arr) {
    // 外层循环控制变量交换
    for (let i = 0; i < arr.length - 1; i++) {
      let index = i;
      // 内层循环控制交换位置（或者可以理解为从哪里开始交换）
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[index] > arr[j]) {
          index = j;
        }
      }
      swap(arr, i, index);
    }
    return arr;
  }
  // 时间复杂度：平均时间复杂度是O(n^2)，这是一个不稳定的算法，因为每次交换之后，它都改变了后续数组的顺序。
  // 空间复杂度：辅助空间是常数，空间复杂度为O(1);
}

{
  // 快速排序
  // 首先，我们需要找到一个基数，然后将比基数小的值放在基数的左边，将比基数大的值放在基数的右边，之后进行递归那两组已经归类好的数组。
  function quickSort(arr) {
    if (arr.length <= 1) {
      return arr;
    }
    let temp = arr[0];
    let left = [];
    let right = [];
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] > temp) {
        right.push(arr[i]);
      } else {
        left.push(arr[i]);
      }
    }
    return quickSort(left).concat([temp], quickSort(right));
  }
  // 时间复杂度：平均时间复杂度O(nlogn)，只有在特殊情况下会是O(n^2)，不过这种情况非常少
  // 空间复杂度：辅助空间是logn，所以空间复杂度为O(logn)

  // 巧用es6的方法递归
  function quickSort(arr) {
    if (arr.length <= 1) {
      return arr;
    }
    let [first, ...rest] = arr;
    return [
      ...quickSort(rest.filter((v) => v < first)),
      first,
      ...quickSort(rest.filter((v) => v >= first)),
    ];
  }
  console.log(quickSort([1, 3, 5, 12, 23, 2]));
}
